1. Field of the Invention
The present invention relates to integrated circuit devices generally and more particularly to a semaphore for shared memory cells.
2. Description of the Prior Art
Often times it is useful to share resources, such as, for example, buses, peripherals, and/or memory cells. However, in some situations, it is also necessary to provide some restrictions on that use. One method of limiting the use of a resource is by means of a "software semaphore" of the type which was disclosed entitled `The Structure of "THE"-Multiprogramming System` by E. W. Dijkstra in the "Communications of ACM" 11,5 of May 1968 on pages 341-346.
As an example of such a (simple, binary) semaphore, consider the sitaution in which it is desired that the use of a resource be shared by two processors, but access to the resource be limited to one processor at a time. A certain cell (location) in memory, which is accessible (shared) by both of the processors, could be designated for use in controlling access to the resource. A certain number (zero, for example) could be stored in the memory cell when the resource is not in use (available); and, another number (one, for example) could be stored in the memory cell when the resource is in use (busy). Before a processor is allowed to use the resource, the processor could be required to do the following tasks. First, the processor could be required to "read" from the memory cell (to obtain the number stored therein). Second, the processor could be required to "test" the number read (to determine its value, whether it is a zero or a one). Third, if the results of the test indicate that the resource is not in use (the number read is a zero), the processor could be required to "write" (a one) into the memory cell to indicate that the resource is in use. (If the results of the test indicate that the resource is in use (the number read is a one), the processor could be required to continue reading and testing until the resource is not in use (the number read is a zero).) Finally, when the processor is through with the resource, the processor could be required to "write" (a zero) into the memory cell to indicate that the resource is no longer in use.
Unfortunately, a period of time elapses between the time when one of the processors reads (a zero) from the memory cell and the time when that processor writes (a one) into the memory cell. During this period of time, the other processor could read from the memory cell and conclude that the resource is not in use, and, thus, available. As a consequence, both processors could attempt to use the resource at the same time. (The period of time can be reduced, but not eliminated, if the order of the tasks is changed to require that the processor write before testing.)
Memory devices of the type which are designated IDT7132 by Integrated Device Technology Inc., AMD2130 by Advanced Micro Devices Inc., and 5132 by Vitalic are suitable for shared use by two processors. The IDT7132 device employs what is referred to in the specification sheet for the device as an "arbitration circuit", a circuit for preventing both processors from using the same memory cell at the same time. Included in the arbitration circuit is what is referred to herein as an "arbitrator", specifically, a first and a second NOR gate. One of the inputs of the first NOR gate is connected to the output of the second NOR gate one of the inputs of which is connected to the output of the first NOR gate. In the arbitration circuit, signals developed by the NOR gates are used to develop a pair of (active low) "busy" signals. The busy signals are used to make one of two processors wait while the other processor is using the same memory cell.
Unfortunately, use of the above mentioned memory device and/or arbitration circuit does not solve the above mentioned problem with the software semaphore. Also, for proper operation, the above mentioned arbitration circuit requires the use of processors which have wait capability. Further, the above mentioned memory device and/or arbitration circuit only prevents the simultaneous use of the same memory cell. Some applications require that the use, by a processor, of a series of memory cells be uninterrupted.
In some of these applications timing is critical. For example, once a processor has started reading data from a series of memory cells and writing the data onto a disk or has started reading data from a disk and writing the data into a series of memory cells, it is important that the processor not be interrupted (since the disk won't wait).
In other applications it is important that the use of a series of memory cells by a processor be uninterrupted so as to prevent the use of incomplete and/or erroneous data. As an example, consider video displays in which a master processor generates a picture layout in the form of a display list and a slave processor reads the display list, interprets the list, and generates a raster image in a display buffer. As the raster image in the display buffer is put onto a video screen, the display buffer is wiped clean (in order to achieve high speed animation). As a consequence, the slave processor must continually update the display buffer. To prevent the slave processor from using an imcomplete display list, two display lists are used each stored in a separate series of memory cells. While the slave processor is using one display list to generate the raster image in the display buffer, over and over again, the master processor is generating and/or updating the other display list.
Thus, a need exists for an unambiguous semaphore suitable for insuring the uninterrupted use, by a processor, of a series of memory cells.